class Dijkstra
  NODE_NOT_FOUND = -1
  INFINITY = 1.0/0 # What about an INFINITY constant???
  
  # nodes: GraphNode
  def Dijkstra.compute_min_distances(start_node_idx, nodes)
    visiteds, distances, previouses = setup_data(start_node_idx, nodes)
    
    while(true) do
      curr_idx = pick_smaller_non_visited(visiteds, distances)
      
      if curr_idx == NODE_NOT_FOUND then
        break
      else
        visiteds[curr_idx] = true
      end
      
      curr_node = nodes[curr_idx]
      dist_start_to_curr = distances[curr_idx]
      
      for edge in curr_node.edges
        next_node_idx = nodes.index(edge.node)
        
        dist_start_to_next_though_curr = dist_start_to_curr + edge.distance
        dist_start_to_next = distances[next_node_idx]
        
        if dist_start_to_next_though_curr < dist_start_to_next then 
          distances[next_node_idx] = dist_start_to_next_though_curr
          previouses[next_node_idx] = curr_idx
        end
      end
    end
    
    distances
  end
    
  def Dijkstra.setup_data(start_node_idx, nodes)
    distances = [INFINITY] * nodes.size
    distances[start_node_idx] = 0.0
    for edge in nodes[start_node_idx].edges
      node_idx = nodes.index(edge.node)
      distances[node_idx] = edge.distance
    end
    
    visiteds = [false] * nodes.size
    visiteds[start_node_idx] = true
    
    previouses = [start_node_idx] * nodes.size
    
    [visiteds, distances, previouses]
  end
  
  def Dijkstra.pick_smaller_non_visited(visiteds, distances)
    # muhahahahahahah
#    (0...5).zip(visiteds, distances).inject([NODE_NOT_FOUND, INFINITY]) {|curr_min, node| ! visiteds[node[0]] && distances[node[0]] < curr_min[1] ? [[node[0]], distances[node[0]]] : curr_min }
    
    curr_min = [NODE_NOT_FOUND, INFINITY]

    visiteds.zip(distances).each_with_index do |data, i| # let's be creative anyway
      not_visited = ! visiteds[i]
      less_dist = distances[i] < curr_min[1]
      
      curr_min = [i, distances[i]] if not_visited && less_dist
    end
    
    curr_min[0]
  end
end
